package com.pan.alg.niuke.tree;

import java.util.LinkedList;
import java.util.Queue;

public class TreeSerializeAndDeSerialize {



    String Serialize(TreeNode root) {
        if(root==null){
            return "{}";
        }
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.offer(root);
        while (!treeNodes.isEmpty()){
            int size = treeNodes.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = treeNodes.poll();
                if(-1==poll.val){
                    sb.append("#");
                }else {
                    sb.append(poll.val);
                }
                sb.append(",");
                if(poll.left!=null){
                    treeNodes.offer(poll.left);
                }else if(poll.left==null&&poll.right!=null){
                    treeNodes.offer(new TreeNode(-1));
                }

                if(poll.right!=null){
                    treeNodes.offer(poll.right);
                }else if(poll.right==null&&poll.left!=null){
                    treeNodes.offer(new TreeNode(-1));
                }

                if(-1!=poll.val&&poll.right==null&&poll.left==null&&i<size-1){
                    treeNodes.offer(new TreeNode(-1));
                    treeNodes.offer(new TreeNode(-1));
                }
            }
        }
        String str = sb.toString();
        while(str.endsWith("#,")){
            str = str.substring(0,str.lastIndexOf("#,"));
        }
        str = str.substring(0,str.lastIndexOf(","));
        return "{"+str+"}";
    }



    TreeNode Deserialize(String stro) {
        if("{}".equals(stro)){
            return null;
        }
        String str = stro.substring(1,stro.lastIndexOf("}"));
        String[] split = str.split(",");
        TreeNode head = new TreeNode(Integer.valueOf(split[0]));
        Queue<TreeNode> queues = new LinkedList<>();
        queues.offer(head);
        int index=0;
        while(!queues.isEmpty()&&index<split.length){
            int size = queues.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queues.poll();
                index++;
                if(index<split.length){
                    String s = split[index];
                    if(!"#".equals(s)){
                        node.left=new TreeNode(Integer.valueOf(s));
                        queues.add(node.left);
                    }
                }
                index++;
                if(index<split.length){
                    String s = split[index];
                    if("#".equals(s)){
                        continue;
                    }else{
                        node.right=new TreeNode(Integer.valueOf(s));
                        queues.add(node.right);
                    }
                }
            }
        }
        return head;
    }

    public static void main(String[] args) {
        String ss = "{1,2,3,#,#,6,7}";
        TreeSerializeAndDeSerialize t = new TreeSerializeAndDeSerialize();
        TreeNode deserialize = t.Deserialize(ss);
        String serialize = t.Serialize(deserialize);
        System.out.println(serialize);

        TreeUtil.printTree(deserialize);

    }
}
